% this file is called up by thesis.tex
% content in this file will be fed into the main document

%: ----------------------- name of chapter  -------------------------
\chapter{Controlling negative diffusion} % top level followed by section, subsection
\label{chapter:game}

%: ----------------------- contents from here ------------------------

In Chapter \ref{chapter:discovery} and Chapter \ref{chapter:token}, we
have studied how to enable positive diffusion under both organic and
adversarial dynamics. In this chapter, we switch gear to controlling
negative diffusion.

Over the recent decades, there has been an explosive growth in the use
of personal digital devices of various kinds. This has, unfortunately,
been accompanied by significant increase in worm attacks. While,
effective anti-virus software and patches are readily available, the
average user is very independent and does not often loading these
latest patches due to software cost and other efforts involved. Also
if enough other nodes in the network are secured, the likelihood of a
specific device getting infected would go down, leading to a natural
game theoretic scenario. Aspnes et al~\cite{AspnesCY2006} introduced
an innovative game for modeling the containment of the spread of
viruses and worms (security breaches) in a network.  In this model,
nodes choose to install anti-virus software or not on an individual
basis while the viruses or worms start from a node chosen uniformly at
random and spread along paths consisting of insecure nodes.  They
showed the surprising result that a pure Nash Equilibrium always
exists when all nodes have identical installation costs and identical
infection costs.

In this chapter we present a substantial generalization of the model
of~\cite{AspnesCY2006} that allows for arbitrary security and
infection costs, and arbitrary distributions for the starting point of
the attack.  More significantly, our model $\GNS{d}$ incorporates a
network locality parameter $d$ which represents a hop-limit on the
spread of infection as accounted for in the strategic decisions, due
to either the intrinsic nature of the infection or the extent of
neighborhood information that is available to a node.

We determine that the network locality parameter plays a key role in
the existence of pure Nash equilibria (NE): local ($d = 1$) and global
games ($d = \infty$) have pure NE, while for $\GNS{d}$ games with $1 <
d < \infty$, pure NE may not exist, and in fact, it is NP-complete to
determine whether a given instance has a pure NE.  For local and
global games, we also characterize the price of anarchy in terms of
the maximum degree and vertex expansion of the contact network; these
suggest natural heuristics to aid a network planner in enforcing
efficient equilibria.

We design a general LP-based framework for approximating the
NP-complete problem of finding a socially optimal configuration in our
game.  Our framework yields a $2d$-approximation for general
$\GNS{d}$ games, and an $O(\log n)$-approximation for the global model
where $n$ is the number of network nodes; the latter result
improves on the approximation bound of $O(\log^{1.5}{n})$ of
\cite{AspnesCY2006} achieved for a special case of our global model.

We study the characteristics of NE and the quality of our
approximations empirically in two distinct classes of graphs: random
geometric graphs and power law graphs.  We find that in local and
global games on these real-world networks, best response dynamics
converge in linear or sub-linear time and have costs comparable to the
social optimum.  Finally, we study the performance of our
approximation algorithms, and find that the approximation guarantees
with respect to social cost are much better in practice than our
theoretical bounds.

\input{4_game/relatedwork}
\input{4_game/model}
\input{4_game/Nash}	
\input{4_game/social}
\input{4_game/experiments}
\input{4_game/discussion}

% ---------------------------------------------------------------------------
%: ----------------------- end of thesis sub-document ------------------------
% ---------------------------------------------------------------------------

